from another_version2 import *
import string

#clean the code from unuseful stuff
def clean_code(line):
	line = line.replace("\n"," ");
	return line
	
	
#recognize an instruction and split it into a list of elements like ['move','$regA,'$regB']
def instruction_split(linep):
	end = ""
	index = string.find(linep, "#")
	line = linep
	if index != -1:
		line = linep[:index]
		end = linep[index:]

	line = filter(None, line.split("\t"))
	for	elem in line:
		line2 = filter(None, elem.split(" |,"))
		if len(line2)!=1:
			line.pop(line.index(elem))
			line = line + line2
	if len(end) != 0:
		return line
	else:
		return line
	
	
#recognize an instruction and join it into assembler mode
def instruction_join(lineinlist):
	line=""
	if len(lineinlist)>2:
		for	elem in lineinlist:
			if lineinlist[0][0]!="." or lineinlist[0]==".frame" or lineinlist[0]==".mask" or lineinlist[0]==".fmask":
				if lineinlist.index(elem)==0:
					line="    "+lineinlist[0]+" "
				elif lineinlist.index(elem)==len(lineinlist)-1:
					line=line+lineinlist[lineinlist.index(elem)]
				else:
					line=line+lineinlist[lineinlist.index(elem)]+","
			else:
                                if lineinlist.index(elem)==0:
					line="    "+lineinlist[0]+" "
				elif lineinlist.index(elem)==len(lineinlist)-1:
					line=line+lineinlist[lineinlist.index(elem)]
				else:
					line=line+lineinlist[lineinlist.index(elem)]+" "			
	elif len(lineinlist)==2:
		line="    "+lineinlist[0]+" "+lineinlist[1]
	elif len(lineinlist)<2 and len(lineinlist)>0:
		if lineinlist[0][0]!=".":
			line=lineinlist[0]
		else:
			line="    "+lineinlist[0]
	else:
		line=lineinlist[0]

	return line
	
#pop a number of elements that you decide from a list item you choose
def poplist_from_index_for_numelem(content,index,numelem):
	for i in range(int(index+1),int(index+numelem+1)):
		content.pop(i)
		content.insert(i,instruction_join(["\n"])) 
	return int(i)







#return the line number of a jump instruction
def jump_to_line(content,linepass,registers):
	if linepass[0]=="j": # or linepass[0]=="jal":
		registers = pop_dead_registers(registers)
		#print "********trovata jump!!!!"
		for i in range(0,len(content)):
			line = content[i]
			line = clean_code(line)
			linex = instruction_split(line)
			#print "--->"+str(linex)
			if line.rstrip():
				if(linex[0]==linepass[1]+":"):
					#print "Sono Ugualiiiiii vado alla riga --->"+str(i)
					return [i,registers]
		return False
	else:
		#print False
		return False
	
#return the line number of a branch instruction
def branch_to_line(content,linepass,registers):
	if linepass[0]=="bne":
		#print "********trovata branch!!!!"
		if int(register_value(linepass[1],registers))!=int(register_value(linepass[2],registers)):
			#print "ENTRATTTTTTOOOO"
			registers = pop_dead_registers(registers)
			for i in range(0,len(content)):
				line = content[i]
				line = clean_code(line)
				linex = instruction_split(line)
				#print "--->"+str(linex)
				if line.rstrip():
					if(linex[0]==linepass[3]+":"):
						#print "Sono diversiiiii vado alla riga --->"+str(i)
						return [i,registers]
		else:
			return False
	elif linepass[0]=="beq":
		#print "********trovata branch!!!!"
		if int(register_value(linepass[1],registers))==int(register_value(linepass[2],registers)):
			#print "ENTRATTTTTTOOOO"
			registers = pop_dead_registers(registers)
			for i in range(0,len(content)):
				line = content[i]
				line = clean_code(line)
				linex = instruction_split(line)
				#print "--->"+str(linex)
				if line.rstrip():
					if(linex[0]==linepass[3]+":"):
						#print "Sono diversiiiii vado alla riga --->"+str(i)
						return [i,registers]
		else:
			return False
	else:
		return False

#pop dead registers
def pop_dead_registers(registers):
	length=len(registers)
	for i in range(0,length):
		if i<length :
			if registers[i][0]=="$4" or registers[i][0]=="$5" or registers[i][0]=="$6" or registers[i][0]=="$7" or registers[i][0]=="$8" or registers[i][0]=="$9" or registers[i][0]=="$10" or registers[i][0]=="$11" or registers[i][0]=="$12" or registers[i][0]=="$14" or registers[i][0]=="$15" or registers[i][0]=="$24" or registers[i][0]=="$25":
				registers.pop(i)
				length=length-1
	return registers
	
#dataflow analysis
def dataflow_analysis(lineinlist,registers):
	if len(lineinlist)>2 and len(registers)>0:
		for i in range(0,len(registers)):
			if registers[i][0]==lineinlist[1] and lineinlist[0]!="sw":
				value=mips_operations(lineinlist,registers) #here there is a function that does the calculations every time
				if(value!=None):
					registers[i][1]=value
				break 
			elif registers[i][0]==lineinlist[2] and lineinlist[0]=="sw":
				value=mips_operations(lineinlist,registers) #here there is a function that does the calculations every time
				if(value!=None):
					registers[i][1]=value				
				break
			elif i==len(registers)-1 and lineinlist[0]!="sw":
				value=mips_operations(lineinlist,registers) #here there is a function that does the calculations every time
				if(value!=None):
					registers.append([lineinlist[1],value]) 
				break
			elif i==len(registers)-1 and lineinlist[0]=="sw":
				value=mips_operations(lineinlist,registers) #here there is a function that does the calculations every time
				if(value!=None):
					registers.append([lineinlist[2],value]) 
				break
	return registers

# understands mips operations and return the value for them	
def mips_operations(lineinlist,registers):
	if len(lineinlist)>2 and len(registers)>0:
		if lineinlist[0]=="addu" or lineinlist[0]=="addi" or lineinlist[0]=="add" or lineinlist[0]=="addiu":
			return int(register_value(lineinlist[len(lineinlist)-2],registers))+int(register_value(lineinlist[len(lineinlist)-1],registers))
		elif lineinlist[0]=="subu" or lineinlist[0]=="sub":
			return int(register_value(lineinlist[len(lineinlist)-2],registers))-int(register_value(lineinlist[len(lineinlist)-1],registers))
		elif lineinlist[0]=="mul" or lineinlist[0]=="mult" or lineinlist[0]=="multu":
			return int(register_value(lineinlist[len(lineinlist)-2],registers))*int(register_value(lineinlist[len(lineinlist)-1],registers))
		elif lineinlist[0]=="div" or lineinlist[0]=="divu":
			return int(register_value(lineinlist[len(lineinlist)-2],registers))/int(register_value(lineinlist[len(lineinlist)-1],registers))
		elif lineinlist[0]=="li":
			return int(lineinlist[len(lineinlist)-1],0)
		elif lineinlist[0]=="slt" or lineinlist[0]=="slti" or lineinlist[0]=="sltu" or lineinlist[0]=="sltiu":
			if(int(register_value(lineinlist[len(lineinlist)-2],registers))<int(register_value(lineinlist[len(lineinlist)-1],registers))):
				return 1
			else:
				return 0
		elif lineinlist[0]=="mov" or lineinlist[0]=="move":
			return int(register_value(lineinlist[len(lineinlist)-1],registers))
		elif lineinlist[0]=="sw":
			return int(register_value(lineinlist[1],registers))
		elif lineinlist[0]=="lw":
			return int(register_value(lineinlist[len(lineinlist)-1],registers))
		else:
			return None
			
#get the actual value of a register and return it
def register_value(element, registers):
	#pop the default element that we don't use
	if(registers[0][0]==0 and registers[0][1]==0 and len(registers)>=2):
		registers.pop(0)
	#check for all the registers stored in the list
	for i in range(0,len(registers)):
		if registers[i][0] == element and not element.isdigit():
			return registers[i][1]
		elif registers[i][0] != element and element.isdigit():
			return int(element)
	return 0







#removes the instruction shift $regA,$regA,0
def shift_regA_regA_0(index, lineinlist):
	if len(lineinlist)==4:
		#print lineinlist
		if (lineinlist[0] == "sll" or lineinlist[0] == "sla" or lineinlist[0] == "srl" or lineinlist[0] == "sra" )  and lineinlist[1] == lineinlist[2] and lineinlist[3]=="0":
			print "shift_regA_regA_0",lineinlist
			all_blocks[index].instructions.remove(lineinlist)
			return "# ERASED --> " + instruction_join(lineinlist)
	r = instruction_join(lineinlist) 
	return r
	

#change the instructions move $regA,$regB & instr $regA,$regA,... INTO instr $regA,$regB,...
def instr_regA_regB_other(lineinlist,lineinlist2):
	if len(lineinlist)==3 and len(lineinlist2)>=4:
		if lineinlist[0] == "move" and (lineinlist2[0] == "move" or lineinlist2[0] == "mov" or lineinlist2[0] == "add" or lineinlist2[0] == "addu" or lineinlist2[0] == "addiu" or lineinlist2[0] == "addi" or lineinlist2[0]=="subu" or lineinlist2[0]=="sub" or lineinlist2[0]=="mul" or lineinlist2[0]=="mult" or lineinlist2[0]=="multu" or lineinlist2[0]=="div" or lineinlist2[0]=="divu" or lineinlist2[0]=="li")  and lineinlist[1] == lineinlist2[1] and lineinlist[1]==lineinlist2[2]:
			output=instruction_join([lineinlist2[0],lineinlist[1],lineinlist[2],lineinlist2[3]])
			skipnuminstr=1
			print "instr_regA_regB_other", lineinlist,lineinlist2
			return [output,skipnuminstr]
	return [instruction_join(lineinlist),-1]

#change the instructions [sw $regA,XXX] & [ld $regA,XXX],... INTO [sw $regA,XXX]
def sw_regA_XXX(lineinlist,lineinlist2):
	if len(lineinlist)>=3 and len(lineinlist2)>=3:
		if lineinlist[0] == "sw" and lineinlist2[0] == "ld"  and lineinlist[1] == lineinlist2[1] and lineinlist[2]==lineinlist2[2]:
			output=instruction_join([lineinlist[0],lineinlist[1],lineinlist[2]])
			skipnuminstr=1
			print "instr_regA_regB_other", lineinlist,lineinlist2
			return [output,skipnuminstr]
	return [instruction_join(lineinlist),-1]
	
#change the instructions [add $regA,$regA,X] & [lw ...,0($regA)],... INTO [lw ...,X($regA)]
def lw_XXX_XregA(lineinlist,lineinlist2):
	if len(lineinlist)>=4 and len(lineinlist2)>=3:
		if lineinlist[0] == "addu" and lineinlist2[0] == "lw"  and "0("+lineinlist[1]+")" == lineinlist2[2] and lineinlist[3].isdigit():
			output=instruction_join([lineinlist2[0],lineinlist2[1],lineinlist[3]+"("+lineinlist[1]+")"])
			skipnuminstr=1
			print "lw_XXX_XregA",lineinlist,lineinlist2
			return [output,skipnuminstr]
	return [instruction_join(lineinlist),-1]
	

#change the instructions [instr $regA,...] & [mov $4,$regA] & [jal XXX] INTO [instr $4,...] & [jal XXX]
def instr_4_XXX(lineinlist,lineinlist2):
	if len(lineinlist)>=4 and len(lineinlist2)==3:
		if (lineinlist[0] == "move" or lineinlist[0] == "mov" or lineinlist[0] == "add" or lineinlist[0] == "addu" or lineinlist[0] == "addiu" or lineinlist[0] == "addi" or lineinlist[0]=="subu" or lineinlist[0]=="sub" or lineinlist[0]=="mul" or lineinlist[0]=="mult" or lineinlist[0]=="multu" or lineinlist[0]=="div" or lineinlist[0]=="divu" or lineinlist[0]=="li") and (lineinlist2[0] == "move" or lineinlist2[0] == "mov") and lineinlist[1]==lineinlist2[2] and (lineinlist2[1]=="$4" or lineinlist2[1]=="$5" or lineinlist2[1]=="$6" or lineinlist2[1]=="$7") :
			output=instruction_join([lineinlist[0],lineinlist2[1],lineinlist[2],lineinlist[3]])
			skipnuminstr=1
			print "instr_4_XXX",lineinlist,lineinlist2
			return [output,skipnuminstr]
	return [instruction_join(lineinlist),-1]
	
#removes the instruction  move_regA_regB
def move_regA_regB(lineinlist,registers):
	if len(lineinlist)==3:
		#print lineinlist
		if (lineinlist[0] == "move" or lineinlist[0] == "move")  and int(register_value(lineinlist[1],registers)) == int(register_value(lineinlist[2],registers)):
			return "# ERASED --> " + instruction_join(lineinlist)
	return instruction_join(lineinlist)

#check for an element inside a multidimensional list
def search_element(element, multilist):
	#check for all the elements stored in the list
	p=0
	for i in multilist:
		if i[0] == element:
			return int(p)
		p+=1
	return False

#create a list with the optimized files instructions
def optimized_list(optlist,instr,linenum,newfile):
	if len(optlist)>0:
		#pop the default element that we don't use
		if(optlist[0][0]==0 and optlist[0][1]==0):
			optlist.pop(0)
		if not search_element(linenum, optlist):
			optlist.insert(linenum,[int(linenum),instr])
			#print optlist                  
	return optlist

#create a list with the optimized files instructions
def optimized_list_into_file(optlist,newfile):
    #sort the list in place
    optlist.sort(key=operator.itemgetter(0))
    f = open(newfile, "w")
    f.close()       
    if len(optlist)>0:
        for i in optlist:
            f = open(newfile, "a")
            f.write(str(i[1])+"\n")
            f.close()
    return optlist

	
#peephole optimizer main
def peephole_optimizer():
	registers=[[0,0]] #default value of the registers list
	foo = open("clinpack_peep_optimized.s", "w")
    #creates a new file for the optimization
	jump = branch = False
	optlist=[[0,0]]

	for block in all_blocks:
		if block.index == 0:
			for k in block.instructions:
				foo.write(k+"\n")
		else:
			i=0
			content = block.instructions
			while (i<len(content)):#content
				line = block.instructions[i] # content[i]
				#clean the line from unuseful stuff
				line = clean_code(line)
				#once he find the main start to optimizee
				if ("#nop" in line) or ("\n" in line) or (not line):
					pass
				else:
					#optimize shift_regA_regA_0
					index = block.index
					r = instruction_split(line)
					line = shift_regA_regA_0(index, r)
					#optimize move_regA_regB
					line = move_regA_regB(instruction_split(line),registers)
					if i+1<len(content):
						#check the next line and clean it
						linenext=clean_code(content[i+1])
					
						#optimize instr_regA_regB_other
						out = instr_regA_regB_other(instruction_split(line),instruction_split(linenext))
						#check if there is somehing else to delete from the list
						if out[1]>-1 and i+int(out[1])<len(content):
							i=poplist_from_index_for_numelem(content,i,out[1])
						#write the new instruction in line var
						line = out[0]
					
						#optimize sw_regA_XXX
						out = sw_regA_XXX(instruction_split(line),instruction_split(linenext))
						#check if there is somehing else to delete from the list
						if out[1]>-1 and i+int(out[1])<len(content):
							i=poplist_from_index_for_numelem(content,i,out[1])
						#write the new instruction in line var
						line = out[0]
					
						#optimize lw_XXX_XregA
						out = lw_XXX_XregA(instruction_split(line),instruction_split(linenext))
						#check if there is somehing else to delete from the list
						if out[1]>-1 and i+int(out[1])<len(content):
							i=poplist_from_index_for_numelem(content,i,out[1])
						#write the new instruction in line var
						line = out[0]

						#optimize instr_4_XXX
						out = instr_4_XXX(instruction_split(line),instruction_split(linenext))
						#check if there is somehing else to delete from the list
						if out[1]>-1 and i+int(out[1])<len(content):
							i=poplist_from_index_for_numelem(content,i,out[1])
						#write the new instruction in line var
						line = out[0]
					
					#dataflow analisys creates a list with the active registers
					registers = dataflow_analysis(instruction_split(line),registers)

					optlist=optimized_list(optlist,line,i,foo)

					#check if there is a jump and if there is jump to that label
					jump=jump_to_line(content,instruction_split(line),registers)

					if jump!=False:
							i=jump[0]-1
							registers=jump[1]

					#check if there is a jump and if there is jump to that label
					branch=branch_to_line(content,instruction_split(line),registers)

					if branch!=False:
							i=branch[0]-1
							registers=branch[1]
					#write the line into the file
					foo.write(line+"\n")

				i = i + 1
	#close the new file
	foo.close()

#call the optimization
peephole_optimizer()
